package com.lry.basic.algorithm.stack;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/5
 */

import java.util.Stack;

/**
 * 给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
 *
 * 你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
 *
 * 在执行完所有删除操作后，返回最终得到的字符串。
 *
 * 本题答案保证唯一。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abcd", k = 2
 * 输出："abcd"
 * 解释：没有要删除的内容。
 *
 * 示例 2：
 *
 * 输入：s = "deeedbbcccbdaa", k = 3
 * 输出："aa"
 * 解释：
 * 先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
 * 再删除 "bbb"，得到 "dddaa"
 * 最后删除 "ddd"，得到 "aa"
 *
 * 示例 3：
 *
 * 输入：s = "pbbcggttciiippooaais", k = 2
 * 输出："ps"
 *

 */
public class RemoveDuplicates {
    public static void main(String[] args) {
        System.out.println(removeDuplicates("deeedbbcccbdaa", 3));
    }

        //deeedbbcccbdaa 3
    public static String removeDuplicates(String s, int k) {
        char[] cs = s.toCharArray();
        char last = cs[0];
        int count = 1;
        int position = -1;
        for (int i = 1; i < cs.length; i++) {
            if(last==cs[i]){
                count++;
                if(count == k){
                    position = i;
                    break;
                }
            }
            else {
                last = cs[i];
                count=1;
            }
        }
        if(position==-1)
            return s;
        else{
            String ns = s.substring(0, position - k+1) + s.substring(position+1);
            return removeDuplicates(ns,k);
        }
    }



}
